(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "Computer Communication network design-experience with theory and practice"

------------------------------<page break>-----------------------------
Computer communication network design 
Experience with theory and practice* 
by HOWARD FRANK 
Network Analysis Corporation 
Glen Cove, New York 
and 
LEONARD KLEINROCK 
University of California 
Los Angeles, California 
ROBERT E. KAHN 
Bolt Beranck and Newman Inc. 
Cambridge, Massachusetts 
INTRODUCTION 
The ARPA Network (ARPANET) project brought 
together many individuals with diverse backgrounds, 
philosophies, and technical approaches from the fields 
of computer science, communication theory, operations 
research and others. The project was aimed at providing 
an efficient and reliable computer communications 
system (using message switching techniques) in which 
computer resources such as programs, data, storage, 
special purpose hardware etc., could be shared among 
computers and among many users? The variety of 
design methods, ranging from theoretical modeling to 
hardware development, were primarily employed 
independently, although cooperative efforts among 
designers occurred on occasion. As of November, 1971, 
the network has been an operational facility for many 
months, with about 20 participating sites, a network 
information center accessible via the net, and well over 
a hundred researchers, system programmers, computer 
center directors and other technical and administrative 
personnel involved in its operation. 
In this paper, we review and evaluate the methods 
used in the ARPANET design from the vantage of 
over two years' experience in the development of the 
network. In writing this paper, the authors have each 
made equal contributions during a series of intensive 
* This work was supported by the Advanced Research Projects 
Agency of the Department of Defense under Contract No. 
DAHC 15-70-C-0120 at the Network Analysis Corporation, 
Contract Nos. DAHC 15-69-C-0179 and DAHC-71-C-0088 at 
Bolt Beranek and Newman Inc., and Contract No. DAHC 
15-69-C-0285 at the University of California at Los Angeles. 
discussions and debates. Rather than present merely a 
summary of the procedures that were used in the 
network design, we trove attempted to evaluate each 
other's methods to determine their advantages and 
drawbacks. Our approaches and philosophies trove often 
differed radically and, as a result, this has not been an 
easy or undisturbing process. On the other hand, we 
have found our collaboration to be extremely rewarding 
and, notably, we have arrived at many similar con- 
clusions about the network's behavior that seem to be 
generally applicable to message switched networks. 
The essence of a network is its design philosophy, its 
performance characteristics, and its cost of implementa- 
tion and operation. Unfortunately, there is no generally 
accepted definition of an "optimal" network or even of 
a "good" network. For example, a network designed to 
transmit large amounts of data only during late evening 
hours might call for structural and performance char- 
acteristics far different from one servicing large numbers 
of users who are rapidly exchanging short messages 
during business hours. We expect this topic, and others 
such a the merits of message switching rs. circuit 
switching or distributed rs. centralized control to be a 
subject of discussion for many years. 
, cost analysis performed in 1967-1968 for the ARPA 
Network indicated that the use of message switching 
would lead to more economical communications and 
better overall availability and utilization of resources 
than other methods. '6. In addition to its impact on 
the availability of computer resources, this decision has 
generated widespread interest in store-and-forward 
communications. In many instances, the use of store- 
and-forward communication techniques can result in 
255 
------------------------------<page break>-----------------------------
256 Spring Joint Computer Conference, 1972 
greater flexibility, higher reliability, significant tech- 
nical advantage, and substantial economic savings over 
the use of conventional common carrier offerings. An 
obvious trend toward increased computer and com- 
munication interaction has begun. In addition to the 
ARPANET, research in several laboratories is under 
way, small experimental networks are being built, and 
a few examples of other government and commercial 
networks are already apparent. 
In the ARPANET, each time-sharing or batch 
processing computer, called a Host, is connected to a 
small computer called an Interface Message Processor 
(IMP). The IMPs, which are interconnected by leased 
50 kilobit/second circuits, 'handle all network eom~ 
munieation for their Hosts. To send a message to 
another Host, a Host precedes the text of its message 
with an address and simply delivers it to its IMP. The 
IMPs then determine the route, provide error control, 
and notify the sender of its receipt. The collection of 
Hosts, IMPs, and circuits forms the message switched 
resource sharing network. A good description of the 
ARPANET, and some early results on protocol develop- 
ment and modeling are given in References 3, 12, 15, 
23 and 38. Some experimental utilization of the 
ARPANET is described in Reference 42. A more recent 
evaluation of such networks and a forward look is 
given in References 35 and 39. 
The development of the Network involved four 
principal activities: 
(1) The design of the IMPs to act as nodal store- 
and-forward switches, 
(2) The topological design to specify the capacity 
and location of each communication circuit 
within the network, 
(3) The design of higher level protocols for the use 
of the network by time-sharing, batch pro- 
ceasing and other data processing systems, and 
(4) System modeling and measurement of network 
performance. 
Each of the first three activities were essentially per- 
formed independently of each other, vhereas the 
modeling effort partly affected the IMP design effort, 
and closely interacted .with the topological design 
project. 
The IMPs were designed by Bolt Beranek and 
Newman Inc. (BBN) and were built to operate in- 
dependent of the exact network connectivity; the 
topological structure was specified by Network Analysis 
Corporation (NAC) using models of network per- 
formance developed by NAC and by the University of 
California at Los Angeles (UCLA). The major efforts 
in the area of system modeling were performed at 
UCLA using theoretical and simulation techniques. 
Network performance measurements have bccn con- 
ducted during the development of the network by 
BBN and by the Network Measurement Center at 
UCLA. To facilitate effective use of the net, higher 
level (user) protocols are under development by a 
group of representatives of universities and rcscareh 
centers. This group, known as the Network Working 
Group, has already specified a Host to Host protocol 
and a Telnet protocol, and is in the process of com- 
pleting other function oriented protocols. . We make 
no attempt to elaborate on the Host to Host protocol 
design problems in this paper. 
THE NETWORK DESIGN PROBLEM 
A variety of performance requirements and system 
constraints were considered in the design of the net. 
Unfortunately, many of the key design objectives had 
to be specified long before the actual user requirements 
could be known. Once the decision to employ message 
switching was made, and fifty kilobit/second circuits 
were chosen, the critical design variables were the 
network operating procedure and the network topology; 
the desired values of throughput, delay, reliability and 
cost were system performance and constraint variables. 
0thcr constraints affected the structure of the network, 
but not its overall properties, such as those arising from 
decisions about the length of time a message could 
remain within the network, the location of IMPs 
relative to location of Hosts, and the number of Hosts to 
be handled by a single IMP. 
In this section, we identify the central issues related 
to IMP design, topological design, and network 
modeling. In the remainder of the paper, we describe 
the major design techniques which have evolved. 
IMP properties 
The key issue in the design of the IMPs was the 
definition of a relationship between the IMP subnet 
and the Hosts to partition responsibilities so that 
reliable and efficient operation would be achieved. The 
decision was made to build an autonomous subnet, 
inde. pendent (as much as possible) of the operation of 
any Host. The subnet was designed to function as a 
"communications system"; issues concerning the use of 
the subnet by the Hosts (such as protocol development) 
were initially left to the Hosts. For reliability, the 
IMPs were designed to be robust against all line failures 
and the vast majority of IMP and Host failures. This 
decision required routing strategies that dynamically 
adapt to changes in the states of IMPs and circuits, 
------------------------------<page break>-----------------------------
Computer Communication Network Design 257 
and an elaborate flow control strategy to protect the 
subnet against Host malfunction and congestion due to 
IMP buffer limitations. In addition, a statistics and 
status reporting mechanism was needed to monitor the 
behavior of the network. 
The number of circuits that an IMP must handle is a 
design constraint directly affecting both the structure 
of the IMP and the topological design. The speed of the 
IMP and the required storage for program and buffers 
depend directly upon the total required processing 
capacity, which must be high enough to switch traffic 
from one line to another when all are fully occupied. Of 
great importance is the property that all IMPs operate 
with identical programs. This technique greatly 
simplifies the problem of network planning and main- 
tenance and makes network modifications easy to 
perform. 
The detailed physical structure of the IMP is not 
discussed in this paper. 2. However, the operating 
procedure, which guides packets through the net, is 
very much of interest here. The flow control, routing, 
and error control techniques are integral parts of the 
operating procedure and can be studied apart from the 
hardware by which they are implemented. Most 
hardware modifications require changes to many 
IMPs already installed in the field, while a change in 
the operating procedure can often be made more 
conveniently by a change to the single operating 
program common to all IMPs, which can then be 
propagated from a single location via the net. 
Topological properties 
The topological design resulted in the specification of 
the location and capacity of all circuits in the network. 
Projected Host--Host traffic estimates were known at 
the start to be either unreliable or wrong. Therefore, 
the network was designed under the assumption of 
equal traffic between all pairs of nodes. (Additional 
superimposed traffic was sometimes included for those 
nodes with'expectation of higher traffic requirements.) 
The topological structure was determined with the aid 
of specially developed heuristic programs to achieve a 
low cost, reliable network with a high throughput and 
a general insensitivity to the exact traffic distribution. 
Currently, only 50 kilobit/second circuits are being 
used in the ARPANET. This speed line was chosen to 
allow rapid transmission of short messages for inter- 
active processing (e.g., less than 0.2 seconds average 
packet delay) as well as to achieve high throughput 
(e.g., at least 50 kilobits/second) for transmission of 
long messages. For reliability, the network was con~ 
strained to have at least two independent paths between 
each pair of IMPs. 
The topological design problem requires consideration 
of the following two questions: 
(1) Starting with a given state of the network 
topology, what circuit modifications are required 
to add or delete a set of IMPs? 
(2) Starting with a given state of network topology, 
when and where should circuits be added or 
deleted to account for long term changes in 
network traffic? 
If the locations of all network nodes are known in 
advance, it is clearly most efficient to design the 
topological structure as a single global effort. However, 
in the ARPANET, as in most actual networks, the 
initial designation of node locations is modified on 
numerous occasions. On each such occasion, the 
topology can be completely reoptimized to determine a 
new set of circuit locations. 
In practice, there is a long lead time between the 
ordering and the delivery of a circuit, and major topo- 
logical modifications cannot be made without sub- 
stantial difficulty. It is therefore prudent to add or 
delete nodes with as little disturbance as possible to 
the basic network structure consistent with overall 
economical operation. Figure i shows the evolution of 
the ARPANET from the basic four IMP design in 1969 
to the presently planned 27 IMP version. Inspection of 
the 24 and 27 IMP network designs reveals a few 
substantial changes in topology that take adwntage of 
the new nodes being added. Surprisingly enough, a 
complete "reoptimization" of the 27 IMP topology 
yields a network only slightly less expensive (about 
I percent) than the present network design? 
Network modets 
The development of an accurate mathematical model 
for the evaluation of time delay in computer networks is 
among the more difficult of the topics discussed in this 
paper. On the one hand, the model must properly 
reflect the relevant features of the network structure 
and operation, including practical constraints. On the 
other hand, the model must result in a mathematical 
formulation which is tractable and from which mean- 
ingful results can be extracted. However, the two 
requirements are often incompatible and we search for 
an acceptable compromise between these two extremes. 
The major modeling effort thus far has been the study 
of the behavior of networks of queues?  This emphasis 
is logical since in message switched systems, messages 
experience queueing delays as they pass from node to 
node and thus a significant performance measure is the 
------------------------------<page break>-----------------------------
258 
Spring Joint Computer Conference, 1972 
SRI UTAH 
 
UCLA 
4-iMP NETWORK- 12/I/69 
(a) ' 
SRI UTAH MIT LINC SRI UTAH ILL MIT 
UCSBi 
UCLA RAND BBN HARV UCLA RAND BBN 
'10-NODE NETWORK- 7/i/70 
(b) 
LINC 
 
CASI 
 
CARN 
 
HARV BURROUGHS 
15-IMP NETWORK- 5/i/71 
McCLELLAN 
SRI UTAHC 
X yusc 
u:) STAN S DC O IMIT O 
UCLA 
CASE 
CARN 
tMITRE 
 ETAC 
RAND TINKER BBN HARV NBS 
24-IMP NETWORK - 4/i/72 
(d) 
SRI LRL UTAH ILL MIT 
LINC 
UCSB' 
RAOC 
UCLA SDC USC BOULDER GWC CASE 
27-iMP NETWORK- PLANNED 
(e) 
Figure 1--The evolution of the AttPANET 
speed at which messages can be delivered. The queueing 
models were developed at a time when there were no 
operational networks available for experimentation and 
model validation, and simulation was the only tool 
capable of testing their validity. The models, which at 
all times were recognized to be idealized statements 
about the real network, were nonetheless crucial to the 
A_RPANET topological design effort since they afforded 
the only known way to quantitatively predict the 
properties of different routing schemes and topological 
structures. The models have been subsequently demon- 
strated to be very accurate predictors of network 
throughput and indispensable in providing analytical 
insight into the network's behavior. 
The key to the successful development of tractable 
models has been to factor the problem into a set of 
simpler queueing problems. There are also heuristic 
design procedures that one can use in this case. These 
procedures seem to work quite well and are described 
later in the paper. However, if one specializes the 
problem and removes some of the real constraints, 
theory and analysis become useful to provide under- 
standing, intuition and design guidelines for the original 
constrained problem. This approach uncovers global 
properties of network behavior, which provide keys to 
good heuristic design procedures and ideal pcrformance 
bounds. 
DESIGN TECHNIQUES 
In this section we describe the approaches taken to 
the design problems introduced in the previous section. 
We first summarize the important properties of the 
ARPANET design: 
(1) A communications cost of less than 30 cents per, 
thousand packets (approximately a megabit). 
(2) Average packet delays under 0.2 seconds through 
the net. 
(3) Capacity for expansion to 64 IMPs without 
major hardwarc or software redesign. 
(4) Average total throughput capability of 10-15 
kilobits/second for all Hosts at an IMP. 
(5) Peak throughput capability of 85 kilobits/second 
' per pair of IMPs in an otherwise unloaded 
network. 
(6) Transparent communications with maximum 
message size of approximately 8000 bits and 
error rates of one bit in 10 2 or less. 
------------------------------<page break>-----------------------------
Computer Communication Network Design 259 
(7) Approximately 98 percent availability of any 
IMP and close to 100 percent availability of all 
operating IMPs from any operable IMP. 
The relationships between the various design efforts 
 are illustrated by these properties. The, topological 
design provides for both a desired average throughput 
and for two or more paths to be fully used for com- 
munication between any pair of Hosts. The operating 
procedure should allow any pair of Hosts to achieve 
those objectives. The availability of IMPs t( com- 
municate reflects both the fact that IMPs are down 
about 2 percent of the time and that the topology is 
selected so that circuit failures contribute little addi- 
tional to the total system downtime. 
IMP design 
The IMP design consists of two closely coupled but 
nonetheless separable pieces--the physical hardware 
specification (based on timing and reliability considera- 
tions and the operating procedure) and the design and 
implementation of the operating procedure using the 
specified IMP hardware. The IMP originally developed 
for the ARPANET contains a 16-bit one microsecond 
computer that can handle a total of about  megabits/ 
second of "useful" information on a total of approxi- 
mately one megabit/second of circuit capacity (e.g., 
twenty 50 kilobit/second circuits). Hardware is likely 
to change as a function of the required IMP capacity 
but an operating procedure that operates well at one 
IMP capacity is likely to be transferable to machines 
that provide different capacity. However, as a network 
grows in size and utilization, a more comprehensive 
operating procedure that takes account of known 
structural properties, such as a hierarchical topology, 
is appropriate. 
Four primary areas of IMP design, namely message 
handling and buffering, error control, flow control, and 
routing are discussed in this section. The IMP provides 
buffering to handle messages for its Host and packets 
for other IMPs. Error control is required to provide 
reliable communication of Host messages in the 
presence of noisy communication circuits. The design 
of the operating procedure should allow high through- 
put in the net under heavy traffic loads. Two potential 
obstacles to achieving this objective are: (1) The net 
can become congested and cause the throughput to 
decrease with increasing looA, and (2) The muting 
procedure may be unable to hvays adapt sufficiently 
fast to the rapid movement of packets to insure efficient 
routing. A flow control and routing procedure is 
needed that can efficiently meet this requirement. 
Message handling and buffering 
In the ARPANET, the maximum message size was 
constrained to be approximately 8000 bits. A pair of 
Hosts will typically communicate over the net via a 
sequence of transmitted messages. To obtain delays of 
a few tenths of a second for such messages and to lower 
the required IMP buffer storage, the IMP program 
partitions each message into one or more packets each 
containing at most approximately 1000 bits. Each 
packet of a message is transmitted independently to 
the destination where the message is reassembled by 
the IMP before shipment to that destination Host. 
Alternately, the Hosts could assume the responsibility 
for reassembling messages. For an asynchronous IMP- 
Host channel, this marginally simplifies the IMP